package proj1;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class MouseInMaze extends Problem {

	LinkedList<Node> queue, path;
	int numberOfExpandedNodes;

	public MouseInMaze(LinkedList<String> operators) {
		super(operators);
		numberOfExpandedNodes = 0;
		queue = new LinkedList<Node>();
		path = new LinkedList<Node>();

	}
	
	/**
	 * checks if a node is the goal node
	 * @param node The node to get check is goal node
	 */
	public boolean goalTest(Node node) {
		return node.state.tiles[0].y == 4;
	}

	/**
	 * function for computing path cost
	 * the cost is how deep the node lies in the search
	 * @param node The node to get the path cost for
	 */
	public void pathCost(Node node) {
		node.pathCost = node.depth;
	}

	public void generateBoard(String strategy) {
		int[][] grid = new int[6][6];

		// generate an empty board
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				grid[i][j] = -1;
			}
		}

		// decide how many tiles we'll have
		int h_max = 8, v_max = 7;
		int h = (int) (Math.random() * h_max), v = (int) (Math.random() * v_max);
		int ii = h + v + 1;
		
		// start populating board with tiles
		Tile[] tiles = new Tile[ii];
		// set mouse
		tiles[0] = (new Tile(0, 2, 0, 2, false));
		grid[2][0] = 0;
		grid[2][1] = 0;
		//set the rest of the tiles
		for (int i = 1; i < ii; i++) {
			Tile t = new Tile(i);
			while (!t.insert(grid))
				;
			tiles[i] = t;
		}

		State Init = new State(grid, tiles, "");
		allNodes.add(new Node(Init, 0, null, 0, 0));

		if (strategy == "GR1" || strategy == "AS1") {

			allNodes.add(new Node(Init, 0, null, 0, Init.blocksInWay()));
		}
		if (strategy == "GR2" || strategy == "AS2") {
			allNodes.add(new Node(Init, 0, null, 0, 4 - Init.tiles[0].y));
		}
	}
	
	/**
	 * This is the search Queuing function it will insert the expanded nodes based on request strategy
	 * @param expanded a list of all nodes expanded from the previous node
	 * @param strategy The Queuing strategy to follow
	 * @param visualize whether console should print steps or not
	 * @param limit	used for iterative deepening strategy otherwise ignored
	 * @param noDuplicates an optimization that checks for nodes already expanded and doesn't enqueue them, default true
	 */
	public void quingFunction(LinkedList<Node> expanded, String strategy,
			boolean visualize, int limit, boolean noDuplicates) {

		List<Node> repeatedNodes = new ArrayList<Node>();

		if(noDuplicates){
			// check for duplicates in the allNodes
			for (int i = 0; i < expanded.size(); i++) {
				for (Node f : allNodes) {
					// System.out.println("compairing");
					// expanded.get(i).state.print();
					// allNodes.get(j).state.print();
					if (expanded.get(i).state.equals(f.state)) {
						repeatedNodes.add(expanded.get(i));
						if (visualize)
							System.out.println("thrown awaaaaaay "
									+ expanded.get(i).state.id);
	
					}
				}
			}
			for (Node a : repeatedNodes) {
				if (expanded.contains(a)) {
					expanded.remove(a);
	
				}
			}
		}
		// a check for the first time since allNodes would be empty
		for (int i = 0; i < expanded.size(); i++) {
			pathCost(expanded.get(i));
			allNodes.add(expanded.get(i));
		}
		
		if (strategy == "BF") { // insert last
			for (Node n : expanded) {
				pathCost(n);
				queue.addLast(n);
			}
		} else if (strategy == "DF") {// insert first
			for (Node n : expanded) {
				pathCost(n);
				queue.addFirst(n);
			}
		} else if (strategy == "DL") {// Depth Limit Search for ID
			for (Node n : expanded) {
				pathCost(n);
				if(n.depth<=limit)
					queue.addFirst(n);
			}
		} else if (strategy == "ID") {
			// DF for each level is empty because ID is implemented in the general search which calls DL instead

		} else if (strategy == "GR1" || strategy == "AS1") {
			// heuristic 1:number of spaces between mouse and exit

			Node temp;
			for (int i = 0; i < expanded.size(); i++) {
				temp = expanded.get(i);
				pathCost(temp);
				temp.heuristic = 4 - temp.state.tiles[0].y;
				sortedInsert(temp, queue, strategy);
			}
		} else if (strategy == "GR2" || strategy == "AS2") {

			// heurisitc2:number of tiles blocking the path+1

			Node temp;
			for (int i = 0; i < expanded.size(); i++) {
				temp = expanded.get(i);
				pathCost(temp);
				temp.heuristic = temp.state.blocksInWay();
				sortedInsert(temp, queue, strategy);
			}
		}

	}
	/**
	 * function for inserting a node into the queue based on the search strategy
	 * used by greedy and A* strategies
	 * @param node the node to insert
	 * @param list the queue
	 * @param strategy the strategy that decides how the node in inserted
	 */
	public static void sortedInsert(Node node, LinkedList<Node> list,
			String strategy) {
		ListIterator<Node> iterator = list.listIterator();

		while (iterator.hasNext()) {

			Node element = iterator.next();

			if (strategy == "AS1" || strategy == "AS2") {
				if ((element.pathCost + element.heuristic > (node.pathCost + node.heuristic))) {
					iterator.previous();
					iterator.add(node);
					return;
				}
			}

			if (strategy == "GR1" || strategy == "GR2") {
				if (element.heuristic > node.heuristic) {
					iterator.previous();
					iterator.add(node);
					return;
				}
			}

		}
		list.addLast(node);
	}

	/**
	 * Method that runs the General search
	 * @param strategy the strategy for the search
	 * @param visualize a boolean for whether to print the search trace or not
	 */
	public static void MiM(String strategy, boolean visualize) {
		Node node;
		LinkedList<String> operators = new LinkedList<String>();// creating list
		int limit = 1;
		// of the
		// operators
		operators.add("up");
		operators.add("down");
		operators.add("left");
		operators.add("right");
		MouseInMaze M = new MouseInMaze(operators);
		M.generateBoard(strategy);
		Node initial = M.allNodes.getFirst();
		M.queue.addFirst(initial);
		while (!M.queue.isEmpty()) {
			node = M.queue.removeFirst();
			M.numberOfExpandedNodes++;
			if (visualize) {
				node.state.print();
				System.out.println("expanded state " + node.state.id
						+ " in level " + node.depth + "\n");

			}
			if (M.goalTest(node)) {
				Node FinalNode = node;
				System.out.println("1)Steps used to reach the solution ");
				System.out.println("------------------------------------------");
				System.out.println("Initial State");
				initial.state.print();
				while (node.parent != null) {
					M.path.addFirst(node);
					node = node.parent;
				}
				for (Node n : M.path) {
					System.out.println(n.state.step);
				}
				System.out.println("Final State");
				FinalNode.state.print();
				System.out.println("------------------------------------------");
				System.out.println("2)Path cost of the solution is "
						+ FinalNode.pathCost);
				System.out.println("3)Solution Found using "
						+ M.numberOfExpandedNodes + " states");
				if(strategy=="ID"){
					System.out.println("4)Solution Found At Depth "+ (limit-1));
				}
				return;
			}
			
			if(strategy=="ID"){ //for iterative deepening
				M.quingFunction(node.expand("DL", visualize), "DL", visualize, limit, true);
				
				if(M.queue.isEmpty()){
					System.out.println("Queue is Empty "+M.queue.isEmpty());
					//if(visualize){
					System.out.println("---------------------------------");
						System.out.println("No solution found at depth limit "+limit+" restarting with depth limit "+(++limit));
					System.out.println("---------------------------------");
					//}
					M.queue.add(initial);
					State.UID = 1; //reset states
					M.allNodes.clear();
				} else {
					System.out.println("limit = "+limit+" node depth = "+node.depth);
				}
			} else {
				M.quingFunction(node.expand(strategy, visualize), strategy, visualize, 0, true);			
			}

		}
		System.out.println("No solution found, sorry try again");
		return;

	}

	/**
	 * Main method
	 * @param args
	 */
	public static void main(String[] args) {

		MiM("BF", true);

	}

}
